In this section, we prove the Theorem 2.1, which states a problem P and its' orthogonal transformed problem Q(P) = {{Qxi}Ni=1,f}have identical optimal solutions if Qis orthogonal matrix: QQT = QTQ = I. As we mentioned in Section 2.2, reward R is a function of a1:T (solution sequences), ||xi xj||i,j {1,...N} (relative distances) and f (nodes features). And Let R (P)is optimal value of problem P: i.e. Then, the remaining proof is to show Q(P)has an identical solution set with P. Let optimal solution set Π (P) = {πi(P)}Mi=1, where πi(P)indicates optimal solution of P and M is the number of heterogeneous optimal solution. Conversely, For any πi(P) Π (P), they have sample optimal value with Q(P): R(πi(P);P) = R (P) = R (Q(P)) Thus, πi(P) Π (Q(P)).

Deep reinforcement learning (DRL)-based combinatorial optimization (CO) methods (i.e., DRL-NCO) have shown significant merit over the conventional CO solvers as DRL-NCO is capable of learning CO solvers less relying on problem-specific expert domain knowledge (heuristic method) and supervised labeled data (supervised learning method). This paper presents a novel training scheme, Sym-NCO, which is a regularizer-based training scheme that leverages universal symmetricities in various CO problems and solutions. Leveraging symmetricities such as rotational and reflectional invariance can greatly improve the generalization capability of DRL-NCO because it allows the learned solver to exploit the commonly shared symmetricities in the same CO problem class. Our experimental results verify that our Sym-NCO greatly improves the performance of DRL-NCO methods in four CO tasks, including the traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), prize collecting TSP (PCTSP), and orienteering problem (OP), without utilizing problem-specific expert domain knowledge. Remarkably, SymNCO outperformed not only the existing DRL-NCO methods but also a competitive conventional solver, the iterative local search (ILS), in PCTSP at 240 faster speed.